Anh em Lưu Bị phát triển thế lực ở Tiểu Bái khiến Lã Bố lo ngại. Lã Bố bèn mang quân tới đánh. Anh em Lưu Bị thua chạy, đến nương nhờ Tào Tháo. Năm 198, Tào Tháo liên hợp với Lưu Bị khởi đại binh đánh Từ châu, hạ thành Hạ Bì, giết chết Lã Bố. Sau đó ông theo Lưu Bị về Hứa Xương, được Tào Tháo phong làm Trung lang tướng.

Năm 199, ông theo Lưu Bị rời Hứa Xương tới Từ châu, ly khai Tào Tháo. Phi dụ cha của Tần Lãng là Tần Nghi Lộc (tướng cũ của Lã Bố) đi theo. Nghi Lộc đi theo Phi, sau lại đổi ý muốn quay lại, bị Phi đâm chết.[8]

Tào Tháo mang quân đánh Từ châu. Ba anh em Trương Phi xung trận thất bại, bị lạc mỗi người một nơi: Lưu Bị chạy sang Hà Bắc theo Viên Thiệu, Quan Vũ phải hàng Tào, còn Trương Phi cầm một cánh quân chạy tới tận Cổ Thành thuộc huyện Chân Dương, quận Nhữ Nam[9]. Tại đây Trương Phi gặp tướng quân Khăn Vàng là Lưu Tiết, bèn hợp quân với nhau làm một cùng nương tựa[10].

Năm 200, Lưu Bị cùng Triệu Vân rời khỏi chỗ Viên Thiệu về Cổ Thành, Nhữ Nam hội với Trương Phi và Lưu Tiết; Quan Vũ cũng đến hội[11]. Cuối năm đó, do giao tranh với Tào Tháo bất lợi, Trương Phi theo Lưu Bị chạy về Kinh châu nương nhờ Lưu Biểu. Ông cùng Lưu Bị đóng đồn ở Tân Dã thuộc quận Nam Dương.